package _02_linked_list.exerc.findmiddle;

import _02_linked_list.exerc.ListNode;
import _02_linked_list.exerc.ListNodeBuilder;
import org.junit.Test;

/**
 * @author: mornd
 * @dateTime: 2023/6/3 - 19:07
 * 查找链表的中间元素，如果链表长度是偶数，则返回右侧节点
 */
public class MyTest {
    @Test
    public void test() {
        ListNode list = ListNodeBuilder.of(new int[]{1, 2, 3, 4});

        System.out.println(foo1(list).val);
    }

    /**
     *  使用快慢指针法(较易理解，效率较高)
     *  快慢指针起点一样，慢指针每次走一步，对应的快指针每次走两步
     *  如果快指针或者 next 指向了 null 则结束操作，此时慢指针指向的就是中间元素
     *
     * @param list
     * @return
     */
    ListNode foo1(ListNode list) {
        /*
            p1
            p2
            1   2   3   null

                p1
                    p2
            1   2   3   null
         */
        ListNode p1 = list;
        ListNode p2 = list;
        while (p2 != null && p2.next != null) {
            p1 = p1.next;
            p2 = p2.next.next;
        }
        return p1;
    }

    // 返回左侧
    ListNode foo2(ListNode list) {
        ListNode p1 = list;
        ListNode p2 = list;
        while (p2 != null && p2.next != null) {
            // 指向左侧
            if (p2.next.next != null) {
                p1 = p1.next;
            }
            p2 = p2.next.next;
        }
        return p1;
    }
}
